﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//这是一个有向的图，需要存在一个从0到n的路径
public class Solution207
{
    IList<IList<int>> edges=new List<IList<int>>();
    int[] visited;
    bool haveRing=false;
    public bool CanFinish(int numCourses, int[][] prerequisites)
    {
        //先建立邻接表,邻接边不确定，所以用链表
        edges = new List<IList<int>>();
        for (int i = 0;i< numCourses; i++)
        {
            edges.Add(new List<int>());
        }


        for (int i = 0; i < prerequisites.Length; i++)
        {
            edges[prerequisites[i][1]].Add(prerequisites[i][0]);
        }

        visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++)
        {
            if (visited[i] == 0)//完成的2，就不访问了
            {
                DFS(i);
            }
           
            
        }

        if (haveRing)
        {
            return false;
        }
        return true;


    }

   void DFS(int curNode)
    {
        visited[curNode] = 1;
        //遍历当前节点的所以临边
        for (int i = 0;i<edges[curNode].Count ; i++) {

            int nextNode = edges[curNode][i];

            if (visited[nextNode] == 0)
            {

                DFS(nextNode);

            }else if (visited[nextNode] == 1)//正在搜索，说明遇到了环
            {
                haveRing=true;
                return;

            }

        
        }

        visited[curNode] = 2;


       


    }
}
class Program207
{
    static void Main207(string[] args)
    {
        Solution207 solution = new Solution207();
        int numCourses = 2;
        int[][] prerequisites = [[1, 0]];
       bool res= solution.CanFinish(numCourses, prerequisites);
        Console.WriteLine(res);
    }
}
